The complete trace in the previous slide confirmed that the total number of comparisons summed to $O(n^2)$, establishing the standard Bubble Sort's average and worst-case time bounds. However, we can introduce an adaptive optimization that significantly improves the best-case performance.
- Worst/Average Case: For a standard implementation, Bubble Sort executes $\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}$ comparisons and swaps regardless of the initial order of the input array $A$. This quadratic performance leads to a time complexity of $O(n^2)$.
- Best Case (Adaptive Optimization): By checking if a swap occurred in a given pass, the algorithm can be adapted to recognize a sorted list and terminate early.
- If the input array $A$ is already sorted (e.g., $A=[1, 2, 5, 6, 8]$), the first pass will complete zero swaps.
- The
swappedflag detects this lack of activity and immediately breaks the outer loop, resulting in a time complexity of $O(n)$ because only one full pass ($n$ comparisons) is performed. - Bubble Sort is considered in-place because it only requires a temporary variable for swapping elements, leading to a space complexity of $O(1)$.
| Case | Time Complexity | Space Complexity | Efficiency Driver |
|---|---|---|---|
| Worst Case | $O(n^2)$ | $O(1)$ | Reverse-sorted input |
| Average Case | $O(n^2)$ | $O(1)$ | Random input |
| Best Case (Optimized) | $O(n)$ | $O(1)$ | Already sorted input |
Python Implementation: optimized_bubble_sort
1def optimized_bubble_sort(A):
2 n = len(A)
3 # Outer loop: passes
4 for i in range(n - 1):
5 swapped = False # Optimization flag reset
6 # Inner loop: comparisons, reduced bounds
7 for j in range(n - 1 - i):
8 # Comparison
9 if A[j] > A[j+1]:
10 A[j], A[j+1] = A[j+1], A[j]
11 swapped = True
12
13 # Adaptive Check for early termination (Best Case: O(n))
14 if swapped == False:
15 break
16 return A